1. Field of the Invention
The present invention relates generally to computer-aided design of vehicles and, more specifically, to a method of real time collision detection between geometric models in the design of a vehicle.
2. Description of the Related Art
Vehicle design, and in particular the design of an automotive vehicle, has advanced to a state in which computer aided design techniques are frequently incorporated in the development of a new vehicle, or redesign of an existing vehicle. At the same time, enhanced visualization software tools have been developed that allow for interactive display and evaluation of large models, including models developed using computer aided design. In the field of vehicle design, the use of both computer aided design and visualization techniques is especially beneficial in designing, packaging and assembling the various systems incorporated within the vehicle, to maximize the design and functional capabilities of these vehicles. Advantageously, potential vehicle system designs can be considered in a timely and cost-effective manner by analyzing a digital representation of a proposed design, versus preparing an actual vehicle model.
Various aspects of the design task for a vehicle include detecting interferences between components, evaluating assembly processes, and understanding vehicle ergonomics. Recently, these types of design tasks have been accomplished using tools such as virtual reality simulations.
A user held interface device, such as a haptic interface, serves as a tactical interface between the user and the virtual world. The haptic interface allows the computing of reaction forces as a result of touching or pushing a virtual object and is a physical device that delivers the computed force to the user through an end effector. An example of such a haptic interface is disclosed in commonly assigned U.S. Pat. No. 5,694,013 to Stewart et al., entitled “Force Feedback Haptic Interface For a Three-Dimensional CAD Surface,” the disclosure of which is incorporated by reference. Advantageously, the haptic device reproduces at a high rate of speed the sensation of freely moving an object within a constrained environment by determining the forces exchanged between the interacting geometries.
Collision detection is one technique used to compute reaction force by determining whether, and by how much, two objects interpenetrate. Various collision detection methods have been utilized in the past. One method involves a volumetric representation that divides a space into small eight-sided units, called voxels. Each voxel is assigned a value of zero if part of free space, or one if part of the object. The set of all voxels is called a voxmap. A collision is determined by computing the discrete position of a point in space in the voxmap and checking if the corresponding element is zero, representing no collision or one, signaling a collision. While this method works well for simple systems, it is less accurate for more complex models, since the size of the individual voxel determines the accuracy of the geometric representation. Also, it is difficult to accurately prepare a voxmap from a model as complex as a CAD model of a vehicle, or convert a modified voxmap back into a CAD model.
Another method of collision detection includes creating a mesh model of the CAD model, which is a collection of polygons describing the surface of the CAD model. While this method works well, the search for a polygon colliding with the haptic device is more time consuming than the voxel method. Also, unless the CAD model is already in a mesh format, the geometry represented by a NURBS format, or other free form representations, have to be translated into a mesh. A disadvantage is a decrease in model fidelity and topology.
Still another method of collision detection includes a tracking algorithm to detect collisions with a free form surface. The tracking algorithm determines a tracking point on the surface of the CAD model using a numerical approximation starting from the closest point calculated during a previous iteration. Thus, once an initial point is found, the motion of a cursor can by tracked over the surface. Only the parametric domain and trim boundaries limit the tracking motion. While tracking algorithms work well for collision detection, it can be difficult and time consuming to find an initial starting point. Also, certain geometric features of a NURBS surface, such as ridges and cusps formed by points and knots need to be considered separately from the other NURBS surfaces of the CAD model. Traditionally, the closest point to a polygonal mesh is found by representing the mesh as an unconnected group of triangles. A map, such as a Voronoi map is used to assign the elements of the polygonal soup to different regions of the map, so that coherence can be exploited to check the distance to only those polygons belonging to regions that neighbor the current location of the potentially colliding point. However, this technique does not take advantage of connectivity between triangles by assuming the mesh represents a manifold and each triangle will have neighboring triangles, and each vertex a set of connected polygons.
Thus, there is a need in the art for an efficient method of real time collision detection between a point and a tessellated mesh of a computer aided design model and force feedback to a user regarding the collision.